|
課程名稱 |
資料庫理論進階專題
Advanced Topics in Database Theory |
|
開課學期 |
104-2 |
|
授課對象 |
電機資訊學院 資訊工程學研究所 |
|
授課教師 |
陳偉松 |
|
課號 |
CSIE7242 |
|
課程識別碼 |
922EU4280 |
|
班次 |
|
|
學分 |
3 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期二8,9(15:30~17:20)星期三9(16:30~17:20) |
|
上課地點 |
|
|
備註 |
本課程以英語授課。上課教室：資546。
總人數上限：25人 |
|
課程簡介影片 |
|
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
In this course we will cover some of three topics in database theory which in my opinion are interesting and relevant to real world applications. Some materials requires a bit of background knowledge such as treewidth, and hypergraphs,
and we will cover them in the class too. I hope that this course can provide necessary exposure for students to the latest topics in database theory.
|
|
課程目標 |
|
|
課程要求 |
|
|
預期每週課後學習時數 |
|
|
Office Hours |
|
|
指定閱讀 |
|
|
參考書目 |
教科書：The materials that we are going to cover can be found in the following books and articles.
_ S. Abiteboul, R. Hull, V. Vianu.
Foundations of Databases. Addison-Wesley, 1995.
Available online: http://webdam.inria.fr/Alice/
_ A. Atserias, M. Grohe, D. Marx.
Size Bounds and Query Plans for Relational Joins.
SIAM Journal on Computing, 42(4):1737--1767 (2013).
_ E. Codd.
A Relational Model of Data for Large Shared Data Banks.
Communications of the ACM, 13(6):377--387 (1970).
_H. Comon, M. Dauchet, R. Gilleron and C. Loding, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi.
Tree Automata Techniques and Applications.
In http://tata.gforge.inria.fr/
_ R. Fagin.
Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. Journal of the ACM, 30(3):514--550 (1983).
_ J. Flum, M. Frick, M. Grohe.
Query evaluation via tree-decompositions.
Journal of the ACM, 49(6):716--752 (2002).
_ G. Gottlob, N. Leone, F. Scarcello.
The complexity of acyclic conjunctive queries.
Journal of the ACM, 48(3):431--498 (2001).
_ M. Mitzenmacher, E. Upfal.
Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
_ H. Ngo, C. Re, A. Rudra.
Skew strikes back: new developments in the theory of join algorithms.
SIGMOD Record 42(4): 5-16 (2013).
_ T. Veldhuizen.
Triejoin: A Simple, Worst-Case Optimal Join Algorithm.
Proceedings of the 17th International Conference on Database Theory (ICDT) 2014, 96--106.
_ M. Yannakakis.
Algorithms for Acyclic Database Schemes.
Proceedings of the 7th international conference on Very Large Data Bases (VLDB) 1981, 82--94. |
|
評量方式
(僅供參考) |
|
|